<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"><html xmlns="http://www.w3.org/1999/xhtml"><head><link rel="stylesheet" type="text/css" href="style.css" /><script type="text/javascript" src="highlight.js"></script></head><body><pre><span class="hs-pragma">{-# LANGUAGE CPP #-}</span><span class="hs-cpp">
#if !defined(TESTING) &amp;&amp; defined(__GLASGOW_HASKELL__)
</span><span class="hs-pragma">{-# LANGUAGE Safe #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#ifdef __GLASGOW_HASKELL__
</span><span class="hs-pragma">{-# LANGUAGE DataKinds, FlexibleContexts #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">#if __GLASGOW_HASKELL__ &gt;= 800
</span><span class="hs-pragma">{-# LANGUAGE MonoLocalBinds #-}</span><span class="hs-cpp">
#endif
</span><span class="hs-cpp">
#include &quot;containers.h&quot;
</span><span>
</span><span id="line-14"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-15"></span><span class="hs-comment">-- |</span><span>
</span><span id="line-16"></span><span class="hs-comment">-- Module      :  Data.IntMap</span><span>
</span><span id="line-17"></span><span class="hs-comment">-- Copyright   :  (c) Daan Leijen 2002</span><span>
</span><span id="line-18"></span><span class="hs-comment">--                (c) Andriy Palamarchuk 2008</span><span>
</span><span id="line-19"></span><span class="hs-comment">-- License     :  BSD-style</span><span>
</span><span id="line-20"></span><span class="hs-comment">-- Maintainer  :  libraries@haskell.org</span><span>
</span><span id="line-21"></span><span class="hs-comment">-- Portability :  portable</span><span>
</span><span id="line-22"></span><span class="hs-comment">--</span><span>
</span><span id="line-23"></span><span class="hs-comment">-- An efficient implementation of maps from integer keys to values</span><span>
</span><span id="line-24"></span><span class="hs-comment">-- (dictionaries).</span><span>
</span><span id="line-25"></span><span class="hs-comment">--</span><span>
</span><span id="line-26"></span><span class="hs-comment">-- This module re-exports the value lazy &quot;Data.IntMap.Lazy&quot; API, plus</span><span>
</span><span id="line-27"></span><span class="hs-comment">-- several deprecated value strict functions. Please note that these functions</span><span>
</span><span id="line-28"></span><span class="hs-comment">-- have different strictness properties than those in &quot;Data.IntMap.Strict&quot;:</span><span>
</span><span id="line-29"></span><span class="hs-comment">-- they only evaluate the result of the combining function. For example, the</span><span>
</span><span id="line-30"></span><span class="hs-comment">-- default value to 'insertWith'' is only evaluated if the combining function</span><span>
</span><span id="line-31"></span><span class="hs-comment">-- is called and uses it.</span><span>
</span><span id="line-32"></span><span class="hs-comment">--</span><span>
</span><span id="line-33"></span><span class="hs-comment">-- These modules are intended to be imported qualified, to avoid name</span><span>
</span><span id="line-34"></span><span class="hs-comment">-- clashes with Prelude functions, e.g.</span><span>
</span><span id="line-35"></span><span class="hs-comment">--</span><span>
</span><span id="line-36"></span><span class="hs-comment">-- &gt;  import Data.IntMap (IntMap)</span><span>
</span><span id="line-37"></span><span class="hs-comment">-- &gt;  import qualified Data.IntMap as IntMap</span><span>
</span><span id="line-38"></span><span class="hs-comment">--</span><span>
</span><span id="line-39"></span><span class="hs-comment">-- The implementation is based on /big-endian patricia trees/.  This data</span><span>
</span><span id="line-40"></span><span class="hs-comment">-- structure performs especially well on binary operations like 'union'</span><span>
</span><span id="line-41"></span><span class="hs-comment">-- and 'intersection'.  However, my benchmarks show that it is also</span><span>
</span><span id="line-42"></span><span class="hs-comment">-- (much) faster on insertions and deletions when compared to a generic</span><span>
</span><span id="line-43"></span><span class="hs-comment">-- size-balanced map implementation (see &quot;Data.Map&quot;).</span><span>
</span><span id="line-44"></span><span class="hs-comment">--</span><span>
</span><span id="line-45"></span><span class="hs-comment">--    * Chris Okasaki and Andy Gill,  \&quot;/Fast Mergeable Integer Maps/\&quot;,</span><span>
</span><span id="line-46"></span><span class="hs-comment">--      Workshop on ML, September 1998, pages 77-86,</span><span>
</span><span id="line-47"></span><span class="hs-comment">--      &lt;http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.37.5452&gt;</span><span>
</span><span id="line-48"></span><span class="hs-comment">--</span><span>
</span><span id="line-49"></span><span class="hs-comment">--    * D.R. Morrison, \&quot;/PATRICIA -- Practical Algorithm To Retrieve</span><span>
</span><span id="line-50"></span><span class="hs-comment">--      Information Coded In Alphanumeric/\&quot;, Journal of the ACM, 15(4),</span><span>
</span><span id="line-51"></span><span class="hs-comment">--      October 1968, pages 514-534.</span><span>
</span><span id="line-52"></span><span class="hs-comment">--</span><span>
</span><span id="line-53"></span><span class="hs-comment">-- Operation comments contain the operation time complexity in</span><span>
</span><span id="line-54"></span><span class="hs-comment">-- the Big-O notation &lt;http://en.wikipedia.org/wiki/Big_O_notation&gt;.</span><span>
</span><span id="line-55"></span><span class="hs-comment">-- Many operations have a worst-case complexity of /O(min(n,W))/.</span><span>
</span><span id="line-56"></span><span class="hs-comment">-- This means that the operation can become linear in the number of</span><span>
</span><span id="line-57"></span><span class="hs-comment">-- elements with a maximum of /W/ -- the number of bits in an 'Int'</span><span>
</span><span id="line-58"></span><span class="hs-comment">-- (32 or 64).</span><span>
</span><span id="line-59"></span><span class="hs-comment">-----------------------------------------------------------------------------</span><span>
</span><span id="line-60"></span><span>
</span><span id="line-61"></span><span class="hs-keyword">module</span><span> </span><span class="hs-identifier">Data.IntMap</span><span>
</span><span id="line-62"></span><span>    </span><span class="hs-special">(</span><span> </span><span class="hs-keyword">module</span><span> </span><span class="annot"><a href="Data.IntMap.Lazy.html"><span class="hs-identifier">Data.IntMap.Lazy</span></a></span><span class="hs-cpp">
#ifdef __GLASGOW_HASKELL__
</span><span class="hs-comment">-- For GHC, we disable these, pending removal. For anything else,</span><span>
</span><span id="line-65"></span><span class="hs-comment">-- we just don't define them at all.</span><span>
</span><span id="line-66"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntMap.html#insertWith%27"><span class="hs-identifier">insertWith'</span></a></span><span>
</span><span id="line-67"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntMap.html#insertWithKey%27"><span class="hs-identifier">insertWithKey'</span></a></span><span>
</span><span id="line-68"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntMap.html#fold"><span class="hs-identifier">fold</span></a></span><span>
</span><span id="line-69"></span><span>    </span><span class="hs-special">,</span><span> </span><span class="annot"><a href="Data.IntMap.html#foldWithKey"><span class="hs-identifier">foldWithKey</span></a></span><span class="hs-cpp">
#endif
</span><span>    </span><span class="hs-special">)</span><span> </span><span class="hs-keyword">where</span><span>
</span><span id="line-72"></span><span>
</span><span id="line-73"></span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Data.IntMap.Lazy.html"><span class="hs-identifier">Data.IntMap.Lazy</span></a></span><span class="hs-cpp">

#ifdef __GLASGOW_HASKELL__
</span><span class="hs-keyword">import</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.TypeError.html"><span class="hs-identifier">Utils.Containers.Internal.TypeError</span></a></span><span>
</span><span id="line-77"></span><span>
</span><span id="line-78"></span><span class="hs-comment">-- | This function is being removed and is no longer usable.</span><span>
</span><span id="line-79"></span><span class="hs-comment">-- Use 'Data.IntMap.Strict.insertWith'</span><span>
</span><span id="line-80"></span><span id="local-6989586621679187846"><span class="annot"><a href="Data.IntMap.html#insertWith%27"><span class="hs-identifier hs-type">insertWith'</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.TypeError.html#Whoops"><span class="hs-identifier hs-type">Whoops</span></a></span><span> </span><span class="annot"><span class="hs-string">&quot;Data.IntMap.insertWith' is gone. Use Data.IntMap.Strict.insertWith.&quot;</span></span><span>
</span><span id="line-81"></span><span>            </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187846"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-82"></span><span id="insertWith%27"><span class="annot"><span class="annottext">insertWith' :: forall a.
Whoops
  &quot;Data.IntMap.insertWith' is gone. Use Data.IntMap.Strict.insertWith.&quot; =&gt;
(a -&gt; a -&gt; a) -&gt; Key -&gt; a -&gt; IntMap a -&gt; IntMap a
</span><a href="Data.IntMap.html#insertWith%27"><span class="hs-identifier hs-var hs-var">insertWith'</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; a -&gt; a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">Key
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">IntMap a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntMap a
forall a. HasCallStack =&gt; a
</span><a href="../../base/src/GHC.Err.html#undefined"><span class="hs-identifier hs-var">undefined</span></a></span><span>
</span><span id="line-83"></span><span>
</span><span id="line-84"></span><span class="hs-comment">-- | This function is being removed and is no longer usable.</span><span>
</span><span id="line-85"></span><span class="hs-comment">-- Use 'Data.IntMap.Strict.insertWithKey'.</span><span>
</span><span id="line-86"></span><span id="local-6989586621679187839"><span class="annot"><a href="Data.IntMap.html#insertWithKey%27"><span class="hs-identifier hs-type">insertWithKey'</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.TypeError.html#Whoops"><span class="hs-identifier hs-type">Whoops</span></a></span><span> </span><span class="annot"><span class="hs-string">&quot;Data.IntMap.insertWithKey' is gone. Use Data.IntMap.Strict.insertWithKey.&quot;</span></span><span>
</span><span id="line-87"></span><span>               </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.IntSet.Internal.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntSet.Internal.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187839"><span class="hs-identifier hs-type">a</span></a></span></span><span>
</span><span id="line-88"></span><span id="insertWithKey%27"><span class="annot"><span class="annottext">insertWithKey' :: forall a.
Whoops
  &quot;Data.IntMap.insertWithKey' is gone. Use Data.IntMap.Strict.insertWithKey.&quot; =&gt;
(Key -&gt; a -&gt; a -&gt; a) -&gt; Key -&gt; a -&gt; IntMap a -&gt; IntMap a
</span><a href="Data.IntMap.html#insertWithKey%27"><span class="hs-identifier hs-var hs-var">insertWithKey'</span></a></span></span><span> </span><span class="annot"><span class="annottext">Key -&gt; a -&gt; a -&gt; a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">Key
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">a
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">IntMap a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">IntMap a
forall a. HasCallStack =&gt; a
</span><a href="../../base/src/GHC.Err.html#undefined"><span class="hs-identifier hs-var">undefined</span></a></span><span>
</span><span id="line-89"></span><span>
</span><span id="line-90"></span><span class="hs-comment">-- | This function is being removed and is no longer usable.</span><span>
</span><span id="line-91"></span><span class="hs-comment">-- Use 'Data.IntMap.Lazy.foldr'.</span><span>
</span><span id="line-92"></span><span id="local-6989586621679187836"><span id="local-6989586621679187837"><span class="annot"><a href="Data.IntMap.html#fold"><span class="hs-identifier hs-type">fold</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.TypeError.html#Whoops"><span class="hs-identifier hs-type">Whoops</span></a></span><span> </span><span class="annot"><span class="hs-string">&quot;Data.IntMap.fold' is gone. Use Data.IntMap.foldr or Prelude.foldr.&quot;</span></span><span>
</span><span id="line-93"></span><span>     </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="#local-6989586621679187837"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187836"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187836"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187836"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187837"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187836"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-94"></span><span id="fold"><span class="annot"><span class="annottext">fold :: forall a b.
Whoops
  &quot;Data.IntMap.fold' is gone. Use Data.IntMap.foldr or Prelude.foldr.&quot; =&gt;
(a -&gt; b -&gt; b) -&gt; b -&gt; IntMap a -&gt; b
</span><a href="Data.IntMap.html#fold"><span class="hs-identifier hs-var hs-var">fold</span></a></span></span><span> </span><span class="annot"><span class="annottext">a -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">IntMap a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b
forall a. HasCallStack =&gt; a
</span><a href="../../base/src/GHC.Err.html#undefined"><span class="hs-identifier hs-var">undefined</span></a></span><span>
</span><span id="line-95"></span><span>
</span><span id="line-96"></span><span class="hs-comment">-- | This function is being removed and is no longer usable.</span><span>
</span><span id="line-97"></span><span class="hs-comment">-- Use 'foldrWithKey'.</span><span>
</span><span id="line-98"></span><span id="local-6989586621679187832"><span id="local-6989586621679187833"><span class="annot"><a href="Data.IntMap.html#foldWithKey"><span class="hs-identifier hs-type">foldWithKey</span></a></span><span> </span><span class="hs-glyph">::</span><span> </span><span class="annot"><a href="Utils.Containers.Internal.TypeError.html#Whoops"><span class="hs-identifier hs-type">Whoops</span></a></span><span> </span><span class="annot"><span class="hs-string">&quot;Data.IntMap.foldWithKey is gone. Use foldrWithKey.&quot;</span></span><span>
</span><span id="line-99"></span><span>            </span><span class="hs-glyph">=&gt;</span><span> </span><span class="hs-special">(</span><span class="annot"><a href="Data.IntSet.Internal.html#Key"><span class="hs-identifier hs-type">Key</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187833"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187832"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187832"><span class="hs-identifier hs-type">b</span></a></span><span class="hs-special">)</span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187832"><span class="hs-identifier hs-type">b</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="Data.IntMap.Internal.html#IntMap"><span class="hs-identifier hs-type">IntMap</span></a></span><span> </span><span class="annot"><a href="#local-6989586621679187833"><span class="hs-identifier hs-type">a</span></a></span><span> </span><span class="hs-glyph">-&gt;</span><span> </span><span class="annot"><a href="#local-6989586621679187832"><span class="hs-identifier hs-type">b</span></a></span></span></span><span>
</span><span id="line-100"></span><span id="foldWithKey"><span class="annot"><span class="annottext">foldWithKey :: forall a b.
Whoops &quot;Data.IntMap.foldWithKey is gone. Use foldrWithKey.&quot; =&gt;
(Key -&gt; a -&gt; b -&gt; b) -&gt; b -&gt; IntMap a -&gt; b
</span><a href="Data.IntMap.html#foldWithKey"><span class="hs-identifier hs-var hs-var">foldWithKey</span></a></span></span><span> </span><span class="annot"><span class="annottext">Key -&gt; a -&gt; b -&gt; b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">b
</span><span class="hs-identifier">_</span></span><span> </span><span class="annot"><span class="annottext">IntMap a
</span><span class="hs-identifier">_</span></span><span> </span><span class="hs-glyph">=</span><span> </span><span class="annot"><span class="annottext">b
forall a. HasCallStack =&gt; a
</span><a href="../../base/src/GHC.Err.html#undefined"><span class="hs-identifier hs-var">undefined</span></a></span><span class="hs-cpp">
#endif
</span></pre></body></html>